Rong Ge, Microsoft Research
In sparse recovery we are given a matrix A \in \R^{n\times m} (“the dictionary”) and a vector of the form AX where X is sparse, and the goal is to recover X. This is a central notion in signal processing, statistics and machine learning. But in applications such as sparse coding, edge detection, compression and super resolution, the dictionary A is unknown and has to be learned from random examples of the form Y = AX where X is drawn from an appropriate distribution — this is the dictionary learning problem. In most settings, A is overcomplete: it has more columns than rows.
A popular algorithm (K-SVD) for dictionary learning uses top singular vectors in alternating minimization. However, no provable guarantee was known until recently. In this talk we show there is a simple algorithm for dictionary learning with provable guarantees. Moreover, K-SVD converges even when the current guess for the dictionary is only slightly correlated with the true dictionary.